Techniques are known for optimizing vehicle routing to replenish inventories in the case of the delivery of consumable products or periodic services using trucks in a multi-stop environment. Industry practices in these areas are set forth below.
Inventory Replenishment-Delivery Economics:
In general, consumption parameters provided by time series forecasting modeling modules calculate expected inventory levels for every day since the last delivery. The expected run out date will occur when the cumulative expected consumption has exhausted the last recorded inventory, which is usually captured at the last delivery. If there were no cost penalty to exhausting inventories, one would wait for that event before triggering replenishment. That would minimize the number of deliveries.
However, since substantial penalties are incurred for exhausting inventories (e.g. running out of propane gas), a classic inventory calculation trading off increased lot size/(decreased annual unit shipping costs) and expected stock out costs/(out of gas penalties) is needed to determine the optimal delivery day (ODD) which therefore occurs sometime before the expected run out day. The smaller the variance (error in predicting consumption) the closer the ODD is to the expected run out day and the steeper the trade off curve. The techniques used in this calculation have long been utilized for inventory reordering in a variety of industrial settings. Typically, the ODD will further be advanced by an additional number of days of reserve, which is the lead time within which a delivery is reasonably assured (e.g. allowing time for a second delivery if the first one failed for any reason). To handle special cases of deliveries, the system will also allow customer specified delivery days that override any statistically determined optimal delivery day.
Optimal Vehicle Routing:
Deliveries, however, cannot be considered independently because they must be combined with other deliveries on a route. To achieve this, commercially available optimal vehicle routing (OVR) packages, which have been readily available for many years, can be used. The basic purpose of OVR packages is to minimize the mileage and travel time costs associated with delivering a number of predetermined loads subject to a vehicle's carrying capacity (e.g. volume, weight) and allowable time on the road. OVR package functionality details often vary. However, all commercial OVR systems assume that deliveries must be made according to a schedule predetermined in the input. So a delivery required for a given day will be assigned to routes specified for a given day or a delivery which is free to be scheduled on several days will be free to be assigned to routes on those days. In other words, OVR systems consider only the geographic efficiencies of the routes generated to guide the assignment and cannot deal with additional complications inherent in delivery of consumable commodities, such as:    (1) OVR packages cannot account for the variation in delivery quantity that would occur if the delivery day were to change, i.e. delivering a time consumable commodity such as propane or fuel oil earlier would result in a smaller load and therefore allow more vehicle capacity for other deliveries and vice-versa.    (2) OVR packages cannot account for the day dependent expected cost of an individual delivery that are derived from inventory replenishment cost trade-offs.
There has been some experimentation in the propane industry with the use of OVR packages but because of the two complications identified above, these exercises have assumed very conservative service policies on delivery day selection (to avoid out of gas conditions). Over time these conservative policies result in the generation of significantly more customer deliveries than would be generated if both temporal (delivery day selection) and geographic (delivery sequencing) dimensions were optimized concurrently. Such optimization is implemented in accordance with the invention.